import java.util.LinkedList;
import java.util.List;

/**
 * @author 03010570
 * @date 2020/06/16
 * describe:    LeetCode: 1431、拥有最多糖果的孩子
 */
public class LeetCode_1244 {
    public static void main(String[] args) {
        int[] candies = new int[]{2, 3, 5, 1, 3};
        int extraCandies = 3;
        List<Boolean> list = kidsWithCandies(candies, extraCandies);
        for (Boolean aBoolean : list) {
            System.out.print(aBoolean + " ");
        }
        System.out.println();
        candies = new int[]{4, 2, 1, 1, 2};
        extraCandies = 1;
        list = kidsWithCandies(candies, extraCandies);
        for (Boolean aBoolean : list) {
            System.out.print(aBoolean + " ");
        }
        System.out.println();
        candies = new int[]{12, 1, 12};
        extraCandies = 10;
        list = kidsWithCandies(candies, extraCandies);
        for (Boolean aBoolean : list) {
            System.out.print(aBoolean + " ");
        }

    }

    /**
     *  思路：
     *      1、第一次循环 找出 最大数s
     *      2、第二次循环判断 当前数+增加数值(extraCandies) 是否可以大于最大数，
     *
     *      时间复杂度： O(2n) ——> O(n)
     *      空间复杂度：O(1)
     * @param candies
     * @param extraCandies
     * @return
     */
    public static List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
        List<Boolean> linkedList = new LinkedList<>();
        int max = Integer.MIN_VALUE;
        for (int candy : candies) {
            if (candy > max) {
                max = candy;
            }
        }
        for (int candy : candies) {
            linkedList.add((candy + extraCandies) >= max);
        }
        return linkedList;
    }
}
